import java.util.Arrays;

public class Solution {
    //暴力，O(n * n)
    public int minSubArrayLen1(int target, int[] nums) {
        int ans = 100001;
        long sum = 0;
        int n = nums.length;
        for(int i = 0; i < n; i++){
            sum = 0;
            for(int j = i; j < n; j++){
                sum += nums[j];
                if(sum >= target){
                    ans = Math.min(ans, j - i + 1);
                    break;
                }
            }
        }
        return ans == 100001 ? 0 : ans;
    }

    //前缀和+二分 O(n * logn)
    int lower_bound(long[] arr, long target){
        int l = 0;
        int r = arr.length - 1;
        while(l <= r){
            int m = l + (r - l) / 2;
            if(arr[m] < target){
                l = m + 1;
            }else{
                r = m - 1;
            }
        }
        return l;
    }

    public int minSubArrayLen2(int target, int[] nums) {
        long[] sum = new long[nums.length + 1];
        //int ans = (int)(1e5 + 1);
        int ans = Integer.MAX_VALUE;
        for(int i = 1; i < sum.length; i++){
            sum[i] = sum[i - 1] + nums[i - 1];
        }
        long s = 0;
        for(int i = 0; i < sum.length; i++){
            s = sum[i] + target;
            //int k = Arrays.binarySearch(sum, s);
            int j = lower_bound(sum, s);
            if(j != sum.length){
                ans = Math.min(ans, j - i);
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }

    //
    public int minSubArrayLen(int target, int[] nums) {
        int i = 0;
        int j = 0;

        long sum = 0;
        int ans = Integer.MAX_VALUE;
        for(j = 0; j < nums.length; j++){
            sum += nums[j];
            while(sum >= target){
                ans = Math.min(ans, j - i + 1);
                sum -= nums[i++];
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}
